#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import defaultdict
from build_directed_graph import *


class DirectedGraphNode:
    # just adjacency list
    def __init__(self, x):
        self.label = x
        self.neighbors = []

    def __str__(self):
        return str(self.label)


# =================== kosaraju算法  =====================
def reverse_graph(graph):
    # 对adjacency list表示的图进行reverse
    # 两次reverse可以还原有向图(无向图不需要reverse)
    reverse_records = defaultdict(list)     # {label : [DirectedGraphNode]}

    # build reverse record
    for node in graph:
        for nei in node.neighbors:
            reverse_records[nei.label].append(node)

    # reverse
    for node in graph:
        node.neighbors = reverse_records[node.label]

def strongly_connected_component_kosaraju(graph):
    # 求有向图的强连通分量个数
    # kosaraju算法, 求解强连通分量.
    reverse_graph(graph)
    reverse_post_order = dfs_post_travel_graph(graph)
    reverse_graph(graph)        # 恢复原图
    # for node in reverse_post_order:
    #     print(node.label)

    visited = set()
    cnts = 0
    while len(visited) != len(graph):
        cur_components = []
        node = reverse_post_order.pop()

        if node in visited:
            # 已经在别的连通分量中了
            continue

        _dfs_post_travel_visited(node, cur_components, visited)
        # print('component %s' % cur_components)
        print('component [', end="")
        for c in cur_components:
            print(c, end=" ")
        print("]")

        cnts += 1

    print("'Kosaraju': count of component %s" % cnts)

def dfs_post_travel_graph(graph):
    if not graph:
        return []

    stack = []
    unvisited = set(graph)

    # while graph:
    #     node = graph.pop()
    while unvisited:
        node = unvisited.pop()
        _dfs_post_travel(node, stack, unvisited)

    return stack

def _dfs_post_travel_visited(node, stack, visited):
    visited.add(node)
    for nei in node.neighbors:
        if nei in visited:
            continue

        visited.add(nei)

        _dfs_post_travel_visited(nei, stack, visited)

    stack.append(node)

def _dfs_post_travel(node, stack, unvisited):
    for nei in node.neighbors:
        if nei not in unvisited:
            continue

        unvisited.remove(nei)

        _dfs_post_travel(nei, stack, unvisited)

    stack.append(node)

# =================== tarjan component =====================
def strongly_connected_component_tarjan(graph):
    # 求无向图的割点
    # tarjan算法 (一次dfs即可)
    non_visited = set(graph)
    ret_components = []
    while non_visited:
        stack = []
        dfn = {}        # {label : dfs_order}
        low = {}        # {label : low}, 节点的子节点最小能够到达的地方
                        # 遍历完毕后: 相同low构成了一个component, dfn == low component结束点
        order = 0
        node = non_visited.pop()

        # 所以可能出现前后两个节点使用相同order:
        # 不过没关系, 前面遍历节点已经处理完毕了, 并且non_visited已更新
        dfs_tarjan_component(node, stack, non_visited, dfn, low, order, ret_components)

    for cur_components in ret_components:
        print('component [', end="")
        for c in cur_components:
            print(c, end=",")
        print("]")

    print('"Tarjan": count of strongly components %s' % len(ret_components))

def dfs_tarjan_component(node, stack, non_visited, dfn, low, order, ret_components):
    label = node.label
    low[label] = dfn[label] = order
    stack.append(node)

    for nei in node.neighbors:
        nei_label = nei.label
        if nei not in non_visited:
            if nei in stack:
                # 如果已经访问过, 但是在栈中(一个前向边), 直接更新low
                low[label] = min(low[label], low[nei_label])
            # else:
            #     # 访问过, 但是不在栈中(横边, 什么都不做)
            #     pass
        if nei in non_visited:
            non_visited.remove(nei)
            nei_low = dfs_tarjan_component(nei, stack, non_visited, dfn, low, order+1, ret_components)
            low[label] = min(low[label], nei_low)

    if dfn[label] == low[label]:
        # print('component %s' % label)
        cur_components = []
        top = stack.pop()
        while top is not node:
            cur_components.append(top)
            top = stack.pop()
        cur_components.append(node)

        ret_components.append(cur_components)

    return low[label]

def is_strongly_connected_graph(graph):
    # 检查一个图是否强连通
    # NOTE: 使用tarjan算法, 从任意节点开始, 只要一次dfs遍历graph: 保证每一个node的low == 0(任何一个节点能到达的最小节点是第一个节点)
    # NOTE: 注意一次dfs完毕后: 检查是否graph都遍历完毕
    non_visited = set(graph)
    ret_components = []
    # while non_visited:
    stack = []
    dfn = {}        # {label : dfs_order}
    low = {}        # {label : low}, 节点的子节点最小能够到达的地方
                    # 遍历完毕后: 相同low构成了一个component, dfn == low component结束点
    order = 0
    node = non_visited.pop()
    print('===================  =====================')
    is_scc, _ = is_strongly_connected_dfs_tarjan(node, stack, non_visited, dfn, low, order)

    # 可能刚好starting point 检查过的节点都在一个cycle中, 但是cycle之外还有其它节点, 这时候判断unvisited长度
    print('is scc top %s' % is_scc)
    if non_visited:
        print("non visited label %s" % non_visited.pop().label)
    return is_scc and len(non_visited) == 0

def is_strongly_connected_dfs_tarjan(node, stack, non_visited, dfn, low, order):
    label = node.label
    low[label] = dfn[label] = order
    stack.append(node)

    for nei in node.neighbors:
        nei_label = nei.label
        if nei not in non_visited:
            if nei in stack:
                low[label] = min(low[label], low[nei_label])

        if nei in non_visited:
            non_visited.remove(nei)
            is_scc, nei_low = is_strongly_connected_dfs_tarjan(nei, stack, non_visited, dfn, low, order+1)
            low[label] = min(low[label], nei_low)
            if not is_scc:
                print('False early : is_scc label, dfn, low (%s, %s, %s) nei_label, nei_low(%s, %s)' % (label, dfn[label], low[label], nei_label, nei_low))
                return False, low[label]

    if low[label] == dfn[label] and dfn[label] != 0:
        # 如果low[label] == dfn[label] : 表示一个component已经遍历完了(如果dfn[label]是0, 那么返回True, 否则图中不止1个连通分量)
        # 如果提前检测到连通分量, 并且不是从dfn == 0开始的(表示不是强连通图)
        is_scc = False
        # print('same     is_scc label, dfn, low (%s, %s, %s)' % (label, dfn[label], low[label]))
    else:
        # print('non-same scc label, dfn, low (%s, %s, %s)' % (label, dfn[label], low[label]))
        assert low[label] < dfn[label]
        # 要保证每个点, 能访问到比自己小的点!
        is_scc = True

    return is_scc, low[label]

# =================== test =====================

def test_reverse_adjacency_list_graph():
    graph = build_directed_graph()
    reverse_graph(graph)
    for node in graph:
        print('label %s, neighbors %s' % (node.label, node.neighbors))
        for nei in node.neighbors:
            print(nei.label)

def test_strong_connected_component():
    # classic example
    # graph = build_directed_graph()
    # strongly_connected_component_kosaraju(graph)

    # graph = build_directed_graph()
    # strongly_connected_component_tarjan(graph)

    graph = build_link_list_like_graph()
    strongly_connected_component_kosaraju(graph)

    graph = build_link_list_like_graph()
    strongly_connected_component_tarjan(graph)

    is_strongly = is_strongly_connected_graph(graph)
    print('link like graph is [%s] strongly connected graph' % is_strongly)

    graph = build_classic_directed_graph()
    strongly_connected_component_kosaraju(graph)

    is_strongly = is_strongly_connected_graph(graph)
    print('classic graph is [%s] strongly connected graph' % is_strongly)

    graph = build_classic_directed_graph()
    strongly_connected_component_tarjan(graph)

def main():
    print("start main")
    # test_reverse_adjacency_list_graph()
    test_strong_connected_component()


if __name__ == "__main__":
    main()
